import java.util.Arrays;

public class WildcardMatching {

	public boolean isMatch(String s, String p) {
		int n = s.length(), m = p.length();
		boolean[][] dp = new boolean[2][n + 1];
		dp[0][0] = true;
		boolean flag;
		for (int i = 1; i <= m; ++i) {
			flag = false;
			Arrays.fill(dp[i % 2], false);
			if (p.charAt(i - 1) == '*') {
				dp[i % 2][0] = dp[(i + 1) % 2][0];
				flag |= dp[i % 2][0];
			}
			for (int j = 1; j <= n; ++j) {
				if (p.charAt(i - 1) == '*') {
					dp[i % 2][j] = dp[i % 2][j - 1] | dp[(i + 1) % 2][j];
				} else if (p.charAt(i - 1) == s.charAt(j - 1)
						|| p.charAt(i - 1) == '?') {
					dp[i % 2][j] = dp[(i + 1) % 2][j - 1];
				}
				flag |= dp[i % 2][j];
			}
			if (!flag) {
				return false;
			}
		}
		return dp[m % 2][n];

	}
}
